

By  complete induction on the depth $k$ of the syntactic dependence tree defining $R$.


\noindent - If $k=0$ then $R$ is a table. Suppose that $d(R)=\multi{\mu_1,\dots,\mu_n}$.
%We distinguish cases depending on the database constraints employed in the definition of $R$.

\input{demotable}

\noindent - If $R$ is a view, then
$\theta(V,d) = \theta(Q,d)\{V.E_1 \mapsto Q.A_1, \dots, V.E_n\mapsto Q.A_n   \}$
with $E_1, \dots, E_n$ the attribute names defined by the view (Def. \ref{def:constraints}), and
$\SQL{V,d} = \SQL{Q,d} \{V.E_1 \mapsto Q.A_1, \dots, V.E_n \mapsto Q.A_n\}$ (Def. \ref{def:sqlop})
and the result is straightforward from the induction hypothesis applied to $Q$.


\noindent - If $R$ is a simple query of the form:

        {\sf
        \begin{tabular}{ll}
        \qquad select $e_1$, \dots, $e_n$ from $R_1\ B_1$ , \dots, $R_m \ B_m$  where $C$; \\
        \end{tabular}
        }

        According to Definition \ref{def:sqlop}

                  \begin{align}
\SQL{Q,d}  = \{ s_Q(\mu) \mid
        \nu_1 \in \SQL{R_1,d}, \dots, \nu_m \in \SQL{R_m,d},  \mu = {\nu_1}^{B_1} \odot \cdots \odot {\nu_m}^{B_m}, \SQL{C\mu,d} \}\label{demo:eq:sql}
        \end{align}

        and by Definition \ref{def:constraints}
        \begin{align}
     \begin{array}{ll}
  \theta(Q,d) = & \multileft{ (\psi_1 \wedge \dots \wedge \psi_m \wedge \ftx{C\mu}{d},\,s_Q(\mu))\ \mid } \\
              & (\psi_1, \nu_1) \in \theta(R_1,d), \dots, (\psi_m, \nu_m) \in \theta(R_m,d),  \mu = {\nu_1}^{B_1} \odot \cdots \odot {\nu_m}^{B_m}   \multiright
  \end{array}
  \label{demo:eq:theta}
        \end{align}


   The first step is to check that
   \begin{align}
   &&&\ftx{C\mu}{d} \textrm { iff } \SQL{C\mu,d} \label{demo:eq:ftxSQL}
   \end{align}
    The result is straightforward from the respective Definitions (\ref{def:sqlop} and \ref{def:constraints}) except in the case of existential subqueries.
   In this case, Definition \ref{def:sqlop} indicates that an existential subquery $Q'$ is transformed into  $\SQL{Q', d} \neq \emptyset$, which
    is true iff there is some $\eta \in \SQL{Q', d}$. By the inductive hypothesis this means that $(true,\eta) \in \theta(Q',d)$. Thus, in the Definition \ref{def:constraints} the multiset
    $\theta(Q',d) = \multi{ (\psi_1, \mu_1), \dots (\psi_{p},\mu_{p}) }$ contains at least one tuple
    $(\psi_{i},\mu_{i})$ with $\psi_i = true$ for some $1 \leq i \leq p$, which implies that
     $\ftx{C\mu}{d} = (\vee_{j=1}^{p} \psi_j)$ is true, proving \ref{demo:eq:ftxSQL}.



   Then, $(true,\eta) \in \theta(Q,d)$ with cardinality $k$ iff there are exactly $k$ values such that for $i=1 \dots k$
        \begin{align}
        &&& \mu_i =  {\nu^i_1}^{B_1} \odot \cdots \odot {\nu^i_m}^{B_m}, \textrm{ for some }  (\psi^i_1, \nu^i_1) \in \theta(R_1,d), \dots, (\psi^i_m, \nu^i_m) \in \theta(R_m,d) \label{demo:eq:mudef} \\
        &&&\eta  = s_Q(\mu_i)   \label{demo:eq:etadef} \\
        &&&\psi^i_1=true, \dots,  \psi^i_m=true \label{demo:eq:psitrue} \\
        &&&\ftx{C\mu}{d}=true \textrm{ and thus by Def. \ref{def:sqlop} } \SQL{C\mu,d}=true  \label{demo:eq:C'true}
        \end{align}

    From    \ref{demo:eq:psitrue} and considering \ref{demo:eq:mudef}, applying the induction hypothesis:
       \begin{align}
        &&&\nu^i_1 \in \SQL{R_1,d}, \dots,  \nu^i_m \in \SQL{R_m,d}, i=1 \dots k \label{demo:eq:nu}
            \end{align}
       and thus $s_Q(\mu_i) \in \SQL{Q,d}$ in  \ref{demo:eq:sql} for $i=1 \dots m$. That is (considering \ref{demo:eq:etadef}), $\eta \in \SQL{Q,d}$ with multiplicity $k$.\smallskip


\noindent - If $R$ is of the form
     \cod{$Q_1$ union $Q_2$}, then $\SQL{Q,d} = \SQL{Q1,d} \cup \SQL{Q2,d}$ (Def. \ref{def:sqlop}),
     $\theta(V_1 \ \textrm{\sf union }\ V_2,d) = \theta({V_1},d)\ \cup\ \theta({V_2},d)$ (Def.
     \ref{def:constraints}), and the result is an easy consequence of the induction hypothesis.

\noindent - If $R$ is a query of the form:
     \cod{$Q_1$ intersection $Q_2$} the result is similar to the previous case and it is omitted
     for the sake of space.
